home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d20 / pvert.arc / BMG.C < prev    next >
Text File  |  1992-01-15  |  4KB  |  135 lines
  1. /*
  2.  *    bmg.c ->    Boyer-Moore-Gosper search routines
  3.  *
  4.  * Adapted from:
  5.  *     Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  6.  *     original paper (CACM, October, 1977).    No delta1 or delta2.  According to
  7.  *     experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  8.  *     practical value.  However, to improve for worst case input, integrating
  9.  *     the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  10.  *     February 1986) deserves consideration.
  11.  *
  12.  *     James A. Woods                 Copyright (c) 1986
  13.  *     NASA Ames Research Center
  14.  *
  15.  * 29 April 1986    Jeff Mogul    Stanford
  16.  *    Adapted as a set of subroutines for use by a program. No
  17.  *    regular-expression support.
  18.  *
  19.  * 29 August 1986    Frank Whaley    Beyond Words
  20.  *    Trimmed for speed and other dirty tricks.
  21.  */
  22. #ifdef OS2
  23.  #define INCL_DOS
  24.  #include <os2.h>
  25. #endif
  26. #include <ctype.h>
  27. #include <string.h>
  28. #include <stdlib.h>
  29. #include <stdio.h>
  30. #include "bmg.h"
  31.  
  32. /*
  33.  *    bmgCompile() -> compile Boyer-Moore delta table
  34.  *
  35.  *    bmgCompile() compiles the delta table for the given search string, and
  36.  *     initializes the search argument structure.  This structure must be
  37.  *     passed to the bmgSearch() function described below.
  38.  */
  39.  
  40.  
  41. void bmgCompile(char *pat, bmgARG *arg, int ignore)
  42.  
  43.     {
  44.     int i,          /*  general ctr     */
  45.         patlen;     /*    pattern length    */
  46.  
  47.  
  48.     patlen = strlen(pat);
  49.  
  50.     strcpy(arg->pat, pat);
  51.     if ((arg->ignore = (char) ignore) != 0)
  52.         strlwr(arg->pat);
  53.  
  54.     memset(arg->delta, patlen, 256);
  55.  
  56.     for (i = 0; i < patlen; ++i)
  57.         arg->delta[pat[i]] = (char) (patlen - i - 1);
  58.  
  59.     if (ignore) /*    tweak upper case if ignore on  */
  60.         for (i = 0; i < patlen; ++i)
  61.             arg->delta[toupper(pat[i])] = (char) (patlen - i - 1);
  62.     }
  63.  
  64.  
  65. /*
  66.  *    bmgSearch() ->    scan for match
  67.  *
  68.  *    bmgSearch() performs a Boyer-Moore-Gosper search of the given buffer
  69.  *     for the string described by the given search argument structure.  The
  70.  *     match action function "action" will be called for each match found.
  71.  *     This function should return non-zero to continue searching, or 0 to
  72.  *     terminate the search.    bmgSearch() returns the total number of
  73.  *   matches found.  (NOTE: this comment appears to be incorrect)
  74.  */
  75.  
  76. char * bmgSearch(char * buffer, size_t buflen, bmgARG *arg)
  77.  
  78.     {
  79.     char    *s;     /*    temp ptr for comparisons    */
  80.     int inc,        /*    position increment        */
  81.         patlen;     /*    pattern length        */
  82.     size_t  k;      /*  current buffer index    */
  83.  
  84.  
  85.     k = (patlen = strlen(arg->pat)) - 1;
  86.  
  87.     for (;;)
  88.         {
  89.         while (((inc = arg->delta[buffer[k]]) != 0) &&
  90.             ((k += inc) < buflen))
  91.             ;
  92.         if (k >= buflen)
  93.             break;
  94.  
  95.         s = buffer + (k++ - (patlen - 1));
  96.         if (!(arg->ignore ? strnicmp(s, arg->pat, patlen) : strncmp(s, arg->pat, patlen)))
  97.             return (s);
  98.         }
  99.  
  100.     return (NULL);
  101.     }
  102.  
  103.  
  104. /* all the above was ripped off from the PD MSGED source by jim nutt */
  105.  
  106.  
  107. char * bmgStrstr (char *find,char *in,int ignore) {
  108.  
  109.     static bmgARG arg;
  110.     static char   last[bmgMAXPAT + 1] = "";
  111.     int           len;
  112.     char          *p;
  113.  
  114.  
  115. #ifdef OS2
  116.     DosEnterCritSec();
  117. #endif
  118.       if(strcmp(last,find)) {
  119.           memset(&arg,0,sizeof(bmgARG));
  120.           memset(last,0,sizeof(last));
  121.           len = strlen(find);
  122.           strncpy(last,find,min(len,bmgMAXPAT));
  123.           bmgCompile(last,&arg,ignore);
  124.       }
  125.       p = bmgSearch(in,strlen(in),&arg);
  126. #ifdef OS2
  127.     DosExitCritSec();
  128. #endif
  129.     return p;
  130. }
  131.  
  132. /*
  133.  *    END of bmg.c
  134.  */
  135.